The network communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs typically require matching packets on a subset of fields of the packet header or flow label with the semantics of a sequential search through the ACL rules.
Access control and quality of service features are typically implemented based on programming contained in one or more ACLs. A network administrator controls access to a network using access control lists (ACLs). ACLs are very flexible and allow the network administrator to specify several conditions to be met and several actions to be taken. The syntax is such that it is most easily interpreted in a serial fashion. When an ACL entry matches a packet in a process of serially evaluating an ACL in a known system, one of the actions that may be required is to skip over a certain number of subsequent ACL entries before resuming the serial evaluation. When implemented by a software program, a serial interpretation is quite natural, however, the number of packets per second that can be processed is limited.
In high performance network switches, a ternary content addressable memory (TCAM) is commonly used to increase the number of packets per second that can be processed as it allows lookup operations to be performed in parallel on numerous entries corresponding to ACL actions. However, the performance advantage of a TCAM is only available if all entries are evaluated at once and a TCAM chip can only provide the address of the first matching entry.
So, to implement features in hardware in which more than one matching condition can be specified, these multiple ACL lists are typically combined into one list using a software merge transformation which can be used for programming and associative memory. Various techniques are known for combining these items, such as Binary Decision Diagram (BDD) and Order Dependent Merge (ODM). For example, if there are two ACLs A (having entries A1 and A2) and B (having entries B1 and B2, then ODM combines these original lists to produce one of two cross-product equivalent ordered lists, each with four entries: A1B1, A1B2, A2B1, and A2B2; or A1B1, A2B1, A1B2, and A2B2.
These four entries can then be programmed into an associative memory and an indication of a corresponding action to be taken placed in an adjunct memory. Lookup operations can then be performed on the associative and adjunct memories to identify a corresponding action to use for a particular packet being processed. There are also variants of ODM and BDD which may filter out the entries which are unnecessary as their values will never allow them to be matched.
However, these software merge techniques can cause each ACL entry to consume multiple entries in the TCAM. To reduce the size of the TCAM, there also exist mechanisms that use multiple ACLs corresponding to multiple groups, and means for merging indications of matching items of multiple groups and possibly associated with skip conditions to identify winning entries of particular use for implementing access control lists. In one embodiment, indications are received from an associative memory bank indicating which locations were matched during a lookup operation. Each of the entries is typically associated with one or more hierarchical groups and a skip or no-skip condition. The matching entries are merged to identify one or more winning entries, these being matching entries not in a group that is skipped. A group is typically skipped if the highest priority matching entry of the particular group is associated with a skip condition. A priority encoder can be used to identify a single highest priority winning entry from the winning entries. So, to implement features in hardware in which more than one matching condition.
While the above described mechanism operates for its intended purpose, the policies and prioritizations among them are generally static. Such polices are typically static and are applied based upon fixed information extracted from recognized network protocol headers in each packet. Roaming capabilities of wireless clients present a challenge to implementation of policy. In wireless networking, some policies are characteristic of the original or home network to which a client is associated or to a client group to which the client belongs. These static, packet-based policy mechanisms, however, do not provide for the application of policies based on information outside of discoverable attributes of the packets themselves, such as connection information associated with a client who has roamed to another network.